1055-股票买卖 II

#personal/blog #algorithm/greedy

题目描述

关系

内容

给定一个长度为 $N$ 的数组，数组中的第 $i$ 个数字表示一个给定股票在第 $i$ 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入格式

第一行包含整数 $N$ ，表示数组长度。

第二行包含 $N$ 个不大于 $10000$ 的正整数，表示完整的数组。

输出格式

输出一个整数，表示最大利润。

数据范围

$1 \leq N \leq 10^{5}$

输入样例 1：

6
7 1 5 3 6 4

输出样例 1：

输入样例 2：

5
1 2 3 4 5

输出样例 2：

输入样例 3：

5
7 6 4 3 1

输出样例 3：

样例解释

样例 1：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。共得利润 4+3 = 7。

样例 2：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

样例 3：在这种情况下, 不进行任何交易, 所以最大利润为 0。

问题分析

最初思路

由于可以无限买入卖出，所以，我的第一印象就是在极小值的时候买股票，在极大值的地方卖股票。

所以，问题就变成了寻找数组中所有的极小值和极大值。

极大值的特征是左右两个数比当前的数小，或者相等。但有几个边界需要考虑，我们假设有三个数 a，b，c：

第一个位置和最后一个位置。如果 $a_{1} < a_{2}$ 那么必须买入，如果 $a_{n - 1} \leq a_{n}$ ，那么必须卖出；
$a = b > c o r a > b = c$ 。此时是极小值，极大值同理；
如果 $a = b = c$ ，既不是极大值也不是极小值，不予考虑，直接考虑下一个位置。

思路分析

实际上，只要第二天的价格高于第一天的就可以卖出了。

证明方法是，任意一个跨度为 n 的交易都可以拆分成相邻两天的交易。

利用反证法证明假设，最优解的方法是在 $a_{1}$ 买入， $a_{2}$ 卖出，那么 $a_{1} a_{2}$ 之间必是递增的。因为如果中间有值大于 $a_{2}$ 那么完全可以在那一天卖出，既然是递增的那么就可以分解成相邻的两天卖出。这里我们证明了凡是最优解都可以分解成这种方法。

现在证明凡是这种方法分解的收获一定大于等于最优解。显然，这种方案已经囊括了序列中所有的递增序列了，所以不可能出现反例。

执行流程设计

总结

代码实现

我的思路

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }
    
    int v1 = 0, v2 = 0;
    if (a[1] < a[2]) v1 = a[1];  
    
    int res = 0;
    for (int i = 2; i <= n - 1; i++) {
        if (a[i - 1] <= a[i] && a[i] > a[i + 1]) {
            v2 = a[i];
            res += v2 - v1;
        } else if (a[i - 1] > a[i] && a[i] <= a[i + 1]) {
            v1 = a[i];
        }
    }
    
    if (a[n - 1] < a[n]) {
        v2 = a[n];
        res += v2 - v1;
    }
    cout << res;
    return 0;
}

yxc

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int res = 0;
    
    for (int i = 1; i <= n - 1; i++) {
        int d = a[i + 1] - a[i];
        
        if (d > 0) {
            res += d;
        }
    }
    
    cout << res;
    return 0;
}